package digui.tree;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @author cyt
 * @create 2020-05-29 15:58
 */
public class VisTree {

    /**
     * 建立 二叉树
     *
     * @param args
     */
    public static void main(String[] args) {

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);

        node1.left = node2;
        node1.right = node3;
        node2.right = node4;
        node3.left = node5;
        node5.left = node6;
        node4.left = node7;
        node3.right = node8;


        // System.out.println(highTree(node1));
        layerVis(node1);
//         indextVis(node1);
//         postVis(node1);
//         preVis(node1);
    }


    /**
     * 先序遍历
     * 1 2 4 7 3 5 6 8
     *
     * @param node
     */
    static void preVis(Node node) {
        if (node == null) return;
        System.out.println(node.val);
        preVis(node.left);
        preVis(node.right);
    }

    /*
    后序遍历
    7 4 2 6 5 8 3 1
     */
    static void postVis(Node node) {
        /**
         *        1
         *   2         3
         *     4     5  8
         *  7       6
         *
         */
        if (node == null) return;
        postVis(node.left);
        postVis(node.right);
        System.out.println(node.val);
    }

    /**
     * 中序遍历
     * <p>
     * 2 7 4 1 6 5 3 8
     *
     * @param node
     */
    static void indextVis(Node node) {
        /**
         *        1
         *   2         3
         *     4     5  8
         *  7       6
         *
         */
        if (node == null) return;
        indextVis(node.left);
        System.out.println(node.val);
        indextVis(node.right);

    }

    /**
     * 层序遍历
     *
     * @param node
     */
    static void layerVis(Node node) {
        Queue<Node> queue = new LinkedList<>();
        if (node == null) return;
        queue.add(node);
        while (!queue.isEmpty()) {
            Node node1 = queue.peek();
            queue.remove();
            System.out.println(node1.val);
            if (node1.left != null) queue.add(node1.left);
            if (node1.right != null) queue.add(node1.right);

        }

    }


    /**
     * 求高度
     *
     * @param node
     */
    static int highTree(Node node) {
        if (node == null) return 0;
        int left = highTree(node.left);
        int right = highTree(node.right);
        return Math.max(left, right) + 1;
    }
}
